/**
 * LeetCode102：二叉树的层序遍历
 * 给定一个二叉树，返回按层序遍历得到的节点值
 * 即逐层从左往右访问所有节点
 */

function TreeNode(val){
    this.val = val;
    this.left = this.right = null;
}

/**
 * @description 层序遍历的遍历方式即广度优先遍历，但要按层级对节点值进行返回
 * @description 方式1：按照广度优先遍历，遍历节点的同时记录节点的层级，然后按照层级将节点值添加在对应的数组中
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
    if (!root){ return []; }
    const q = [[root,0]];
    const res = [];
    while (q.length){
        const [n,l] = q.shift();
        if (!res[l]){
            res.push(n.val);
        }else {
            res[l].push(n.val);
        }
        if (n.left) q.push([n.left,l+1]);
        if (n.right) q.push([n.right,l+1]);
    }
};

/**
 * @description 方式2：遍历树结构，每次将一整个层级的节点依次出栈，并添加到数组中，然后再将下一层级的子节点全部入栈
 * @param {TreeNode} root
 * @return {number[]}
 */
var levelOrder_1 = function (root){
    if (!root){ return [];}
    const q = [root];
    const res = [];
    while (q.length){
        let len = q.length;
        res.push([]);
        //按照当前层级的元素个数，循环将当前层级的元素出栈，将子节点入栈
        while (len--){
            const n = q.shift();
            res[q.length-1].push(n.val);
            if (n.left) q.push(n.left);
            if (n.right) q.push(n.right);
        }
    }
}

//时间复杂度：O(n)
//空间复杂度：O(n)